package com.my.study.structures.sort;

import java.util.Arrays;

/**
 * @author Carlos
 * @version 1.0
 * @Description 基数排序
 * <p>
 * 根据元素的位数从右往左进行桶排序
 * @date 2021/7/26 23:20
 **/
public class RadixSort {

    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};

        sort(arr);
    }


    private static void sort(int[] arr) {

        // 0. 寻找待排序元素中的最大值
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }

        // 得到最大元素的位数
        int maxLength = (max + "").length();


        // 0.定义一个二维数组
        int[][] bucket = new int[10][arr.length + 1];
        // 记录二维数组(每个桶)的数据数量
        int[] bucketElementCount = new int[10];

        for (int i = 0; i < maxLength; i++) {
            for (int j = 0; j < arr.length; j++) {
                int digitOfElement = (arr[j] / (int) Math.pow(10, i)) % 10;
                bucket[digitOfElement][bucketElementCount[digitOfElement]] = arr[j];
                bucketElementCount[digitOfElement]++;
            }
            // 按照这个桶的顺序（一维数组的下标依次取出数据，放入原来的数组）
            int index = 0;
            // 遍历每一个桶
            for (int k = 0; k < bucketElementCount.length; k++) {
                if (bucketElementCount[k] != 0) {
                    for (int l = 0; l < bucketElementCount[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                }
                // 把桶计数清零
                bucketElementCount[k] = 0;
            }
            System.out.println("第" + (i + 1) + "轮：" + Arrays.toString(arr));
        }

    }


//    private static void stepSort(int[] arr) {
//        // 0.定义一个二维数组
//        int[][] bucket = new int[10][arr.length + 1];
//        // 记录二维数组(每个桶)的数据数量
//        int[] bucketElementCount = new int[10];
//
//
//        //==================================== 第一轮，针对每个元素的个位进行排序处理
//
//        for (int j = 0; j < arr.length; j++) {
//            int digitOfElement = arr[j] % 10;
//            bucket[digitOfElement][bucketElementCount[digitOfElement]] = arr[j];
//            bucketElementCount[digitOfElement]++;
//        }
//        // 按照这个桶的顺序（一维数组的下标依次取出数据，放入原来的数组）
//        int index = 0;
//        // 遍历每一个桶
//        for (int k = 0; k < bucketElementCount.length; k++) {
//            if (bucketElementCount[k] != 0) {
//                for (int l = 0; l < bucketElementCount[k]; l++) {
//                    arr[index++] = bucket[k][l];
//                }
//            }
//            // 把桶计数清零
//            bucketElementCount[k] = 0;
//        }
//        System.out.println("第1轮：" + Arrays.toString(arr));
//
//        //==================================== 第二轮，针对每个元素的个位进行排序处理
//
//        for (int j = 0; j < arr.length; j++) {
//            int digitOfElement = (arr[j] / 10) % 10;
//            bucket[digitOfElement][bucketElementCount[digitOfElement]] = arr[j];
//            bucketElementCount[digitOfElement]++;
//        }
//        // 按照这个桶的顺序（一维数组的下标依次取出数据，放入原来的数组）
//        index = 0;
//        // 遍历每一个桶
//        for (int k = 0; k < bucketElementCount.length; k++) {
//            if (bucketElementCount[k] != 0) {
//                for (int l = 0; l < bucketElementCount[k]; l++) {
//                    arr[index++] = bucket[k][l];
//                }
//            }
//            // 把桶计数清零
//            bucketElementCount[k] = 0;
//        }
//        System.out.println("第2轮：" + Arrays.toString(arr));
//
//
//        //==================================== 第三轮，针对每个元素的个位进行排序处理
//
//        for (int j = 0; j < arr.length; j++) {
//            int digitOfElement = (arr[j] / 100) % 10;
//            bucket[digitOfElement][bucketElementCount[digitOfElement]] = arr[j];
//            bucketElementCount[digitOfElement]++;
//        }
//        // 按照这个桶的顺序（一维数组的下标依次取出数据，放入原来的数组）
//        index = 0;
//        // 遍历每一个桶
//        for (int k = 0; k < bucketElementCount.length; k++) {
//            if (bucketElementCount[k] != 0) {
//                for (int l = 0; l < bucketElementCount[k]; l++) {
//                    arr[index++] = bucket[k][l];
//                }
//            }
//            // 把桶计数清零
//            bucketElementCount[k] = 0;
//        }
//        System.out.println("第3轮：" + Arrays.toString(arr));
//
//    }

}
